<html>
  <head>
    <meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>1、数据结构之稀疏数组 | 清汤牛肉锅</title>
<meta name="description" content="温故而知新
" />
<link rel="shortcut icon" href="https://ArtZoick.github.io//favicon.ico?v=1572228390311">
<link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.7.2/css/all.css" integrity="sha384-fnmOCqbTlWIlj8LyTjo7mOUStjsKC4pOpQbqyi7RrhN7udi9RwhKkMHpvLbHG9Sr" crossorigin="anonymous">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.10.0/katex.min.css">
<link rel="stylesheet" href="https://ArtZoick.github.io//styles/main.css">

<script src="https://cdn.bootcss.com/highlight.js/9.12.0/highlight.min.js"></script>
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Droid+Serif:400,700">


<script async src="https://www.googletagmanager.com/gtag/js?id=UA-143265163-1"></script>
<script>
  window.dataLayer = window.dataLayer || [];
  function gtag(){dataLayer.push(arguments);}
  gtag('js', new Date());

  gtag('config', 'UA-143265163-1');
</script>


  </head>
  <body>
    <div class="main">
      <div class="main-content">
        <div class="site-header">
  <a href="https://ArtZoick.github.io/">
  <img class="avatar" src="https://ArtZoick.github.io//images/avatar.png?v=1572228390311" alt="">
  </a>
  <h1 class="site-title">
    清汤牛肉锅
  </h1>
  <p class="site-description">
    温故而知新

  </p>
  <div class="menu-container">
    
      
        <a href="/" class="menu">
          首页
        </a>
      
    
      
        <a href="/archives" class="menu">
          归档
        </a>
      
    
      
        <a href="/tags" class="menu">
          标签
        </a>
      
    
      
        <a href="/post/about" class="menu">
          关于
        </a>
      
    
      
        <a href="/post/beef" class="menu">
          牛肉锅
        </a>
      
    
  </div>
  <div class="social-container">
    
      
    
      
    
      
    
      
    
      
    
  </div>
</div>

        <div class="post-detail">
          <article class="post">
            <h2 class="post-title">
              1、数据结构之稀疏数组
            </h2>
            <div class="post-info">
              <span>
                2019-09-27
              </span>
              <span>
                4 min read
              </span>
              
                <a href="https://ArtZoick.github.io//tag/数据结构与算法" class="post-tag">
                  # 数据结构与算法
                </a>
              
            </div>
            
            <div class="post-content-wrapper">
              <div class="post-content">
                <h2 id="1-先看一个实际的需求">1、先看一个实际的需求</h2>
<p>-&gt; 编写的五子棋程序中，有存盘退出和续上盘的功能。</p>
<figure data-type="image" tabindex="1"><img src="https://ArtZoick.github.io//post-images/datastructure/array/1.png" alt=""></figure>
<p>-&gt; 分析问题:<br>
因为该二维数组的很多值是默认值 0, 因此记录了 很多没有意义的数据. -&gt; 稀疏数组。</p>
<h2 id="2-基本介绍">2、基本介绍</h2>
<p>当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。</p>
<p>稀疏数组的处理方法是:</p>
<ol>
<li>记录数组<strong>一共有几行几列，有多少个不同</strong>的值</li>
<li>把具有不同值的元素的行列及值记录在一个小规模的数组中，从而<strong>缩小程序</strong>的规模</li>
</ol>
<img src="file://C:/Users/zoick/OneDrive/Gridea/post-images/datastructure/array/2.png" style="zoom:67%;" />
<h2 id="3-应用实例">3、应用实例</h2>
<h3 id="1-使用稀疏数组来保留类似前面的二维数组棋盘-地图等等">1) 使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)</h3>
<h3 id="2-把稀疏数组存盘并且可以从新恢复原来的二维数组数">2) 把稀疏数组存盘，并且可以从新恢复原来的二维数组数</h3>
<h3 id="3-整体思路分析">3) 整体思路分析</h3>
<img src="file://C:/Users/zoick/OneDrive/Gridea/post-images/datastructure/array/3.png"  />
<h3 id="4-代码实现">4) 代码实现</h3>
<pre><code class="language-java">package datastructure.array;

public class SparseArray {

	public static void main(String[] args) {
		// 创建一个原始的二维数组 11 * 11
		// 0: 表示没有棋子， 1 表示 黑子 2 表蓝子
		int chessArr1[][] = new int[11][11];
		chessArr1[1][2] = 1;
		chessArr1[2][3] = 2;
		chessArr1[4][5] = 2;
		// 输出原始的二维数组
		System.out.println(&quot;原始的二维数组~~&quot;);
		for (int[] row : chessArr1) {
			for (int data : row) {
				System.out.printf(&quot;%d\t&quot;, data);
			}
			System.out.println();
		}

		// 将二维数组 转 稀疏数组的思
		// 1. 先遍历二维数组 得到非0数据的个数
		int sum = 0;
		for (int i = 0; i &lt; 11; i++) {
			for (int j = 0; j &lt; 11; j++) {
				if (chessArr1[i][j] != 0) {
					sum++;
				}
			}
		}

		// 2. 创建对应的稀疏数组
		int sparseArr[][] = new int[sum + 1][3];
		// 给稀疏数组赋值
		sparseArr[0][0] = 11;
		sparseArr[0][1] = 11;
		sparseArr[0][2] = sum;

		// 遍历二维数组，将非0的值存放到 sparseArr中
		int count = 0; //count 用于记录是第几个非0数据
		for (int i = 0; i &lt; 11; i++) {
			for (int j = 0; j &lt; 11; j++) {
				if (chessArr1[i][j] != 0) {
					count++;
					sparseArr[count][0] = i;
					sparseArr[count][1] = j;
					sparseArr[count][2] = chessArr1[i][j];
				}
			}
		}

		// 输出稀疏数组的形式
		System.out.println();
		System.out.println(&quot;得到稀疏数组为~~~~&quot;);
		for (int i = 0; i &lt; sparseArr.length; i++) {
			System.out.printf(&quot;%d\t%d\t%d\t\n&quot;, sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);
		}
		System.out.println();

		//将稀疏数组 --》 恢复成 原始的二维数组
		/*
		 *  1. 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的  chessArr2 = int [11][11]
			2. 在读取稀疏数组后几行的数据，并赋给 原始的二维数组 即可.
		 */

		//1. 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组

		int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];

		//2. 在读取稀疏数组后几行的数据(从第二行开始)，并赋给 原始的二维数组 即可

		for(int i = 1; i &lt; sparseArr.length; i++) {
			chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
		}

		// 输出恢复后的二维数组
		System.out.println();
		System.out.println(&quot;恢复后的二维数组&quot;);

		for (int[] row : chessArr2) {
			for (int data : row) {
				System.out.printf(&quot;%d\t&quot;, data);
			}
			System.out.println();
		}
	}

}

</code></pre>

              </div>
              <div class="toc-container">
                <ul class="markdownIt-TOC">
<li>
<ul>
<li><a href="#1-%E5%85%88%E7%9C%8B%E4%B8%80%E4%B8%AA%E5%AE%9E%E9%99%85%E7%9A%84%E9%9C%80%E6%B1%82">1、先看一个实际的需求</a></li>
<li><a href="#2-%E5%9F%BA%E6%9C%AC%E4%BB%8B%E7%BB%8D">2、基本介绍</a></li>
<li><a href="#3-%E5%BA%94%E7%94%A8%E5%AE%9E%E4%BE%8B">3、应用实例</a>
<ul>
<li><a href="#1-%E4%BD%BF%E7%94%A8%E7%A8%80%E7%96%8F%E6%95%B0%E7%BB%84%E6%9D%A5%E4%BF%9D%E7%95%99%E7%B1%BB%E4%BC%BC%E5%89%8D%E9%9D%A2%E7%9A%84%E4%BA%8C%E7%BB%B4%E6%95%B0%E7%BB%84%E6%A3%8B%E7%9B%98-%E5%9C%B0%E5%9B%BE%E7%AD%89%E7%AD%89">1) 使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)</a></li>
<li><a href="#2-%E6%8A%8A%E7%A8%80%E7%96%8F%E6%95%B0%E7%BB%84%E5%AD%98%E7%9B%98%E5%B9%B6%E4%B8%94%E5%8F%AF%E4%BB%A5%E4%BB%8E%E6%96%B0%E6%81%A2%E5%A4%8D%E5%8E%9F%E6%9D%A5%E7%9A%84%E4%BA%8C%E7%BB%B4%E6%95%B0%E7%BB%84%E6%95%B0">2) 把稀疏数组存盘，并且可以从新恢复原来的二维数组数</a></li>
<li><a href="#3-%E6%95%B4%E4%BD%93%E6%80%9D%E8%B7%AF%E5%88%86%E6%9E%90">3) 整体思路分析</a></li>
<li><a href="#4-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0">4) 代码实现</a></li>
</ul>
</li>
</ul>
</li>
</ul>

              </div>
            </div>
          </article>
        </div>

        
          <div class="next-post">
            <div class="next">下一篇</div>
            <a href="https://ArtZoick.github.io//post/summarize">
              <h3 class="post-title">
                0、数据结构概述
              </h3>
            </a>
          </div>
        

        
          
            <link rel="stylesheet" href="https://unpkg.com/gitalk/dist/gitalk.css">
<script src="https://unpkg.com/gitalk/dist/gitalk.min.js"></script>

<div id="gitalk-container"></div>

<script>

  var gitalk = new Gitalk({
    clientID: 'a2471d09bddb5be481ee',
    clientSecret: '05d427fb27f873cfabace27b9f042f2c7f23000f',
    repo: 'ArtZoick.github.io',
    owner: 'ArtZoick',
    admin: ['ArtZoick'],
    id: (location.pathname).substring(0, 49),      // Ensure uniqueness and length less than 50
    distractionFreeMode: false  // Facebook-like distraction free mode
  })

  gitalk.render('gitalk-container')

</script>

          

          
        

        <div class="site-footer">
  <a href="https://zhidao.baidu.com/question/1867120235416383707.html" target="_blank" onclick="alert('盲生，你发现了华点！');">学习强国</a>

<!--Tido对话插件-->
<script src="//code.tidio.co/5fh6jaqvluqj8jjuf5zlqrf5tlzpktnx.js"></script>
<style>
.text-popup {
    animation: textPopup 1s;
    color: red;
    user-select: none;
    white-space: nowrap;
    position: absolute;
    z-index: 99;
}
@keyframes textPopup {
    0%, 100% {
        opacity: 0;
    }
    5% {
        opacity: 1;
    }
    100% {
        transform: translateY(-50px);    
    }
}
</style>
<script type="text/javascript" src="https://cdn.bootcss.com/canvas-nest.js/1.0.1/canvas-nest.min.js">
!function(){function n(n,e,t){return n.getAttribute(e)||t}function e(n){return document.getElementsByTagName(n)}
function t(){var t=e("script"),o=t.length,i=t[o-1];return{l:o,z:n(i,"zIndex",-1),o:n(i,"opacity",.5),c:n(i,"color","0,0,0")
,n:n(i,"count",99)}}function o(){a=m.width=window.innerWidth||document.documentElement.clientWidth||document.body.clientWidt
h,c=m.height=window.innerHeight||document.documentElement.clientHeight||document.body.clientHeight}function i(){r.clearRect
(0,0,a,c);var n,e,t,o,m,l;s.forEach(function(i,x){for(i.x+=i.xa,i.y+=i.ya,i.xa*=i.x>a||i.x<0?-1:1,i.ya*=i.y>c||i.y<0?-1:1,r.
fillRect(i.x-.5,i.y-.5,1,1),e=x+1;e<u.length;e++)n=u[e],null!==n.x&&null!==n.y&&(o=i.x-n.x,m=i.y-n.y,l=o*o+m*m,l<n.max&&(n===
y&&l>=n.max/2&&(i.x-=.03*o,i.y-=.03*m),t=(n.max-l)/n.max,r.beginPath(),r.lineWidth=t/2,r.strokeStyle="rgba("+d.c+","+(t+.2)+")
",r.moveTo(i.x,i.y),r.lineTo(n.x,n.y),r.stroke()))}),x(i)}var a,c,u,m=document.createElement("canvas"),d=t(),l="c_n"+d.l,r=m.
getContext("2d"),x=window.requestAnimationFrame||window.webkitRequestAnimationFrame||window.mozRequestAnimationFrame||window.
oRequestAnimationFrame||window.msRequestAnimationFrame||function(n){window.setTimeout(n,1e3/45)},w=Math.random,y={x:null,y:nul
l,max:2e4};m.id=l,m.style.cssText="position:fixed;top:0;left:0;z-index:"+d.z+";opacity:"+d.o,e("body")[0].appendChild(m),o(),
window.οnresize=o,window.οnmοusemοve=function(n){n=n||window.event,y.x=n.clientX,y.y=n.clientY},window.οnmοuseοut=function(){y
.x=null,y.y=null};for(var s=[],f=0;d.n>f;f++){var h=w()*a,g=w()*c,v=2*w()-1,p=2*w()-1;s.push({x:h,y:g,xa:v,ya:p,max:6e3})}u=
s.concat([y]),setTimeout(function(){i()},100)}();
</script>

<!--鼠标点击-->
<!--富强-->
<script type="text/javascript"> 
/* 鼠标特效 */ 
var a_idx = 0; 
jQuery(document).ready(function($) { 
    $("body").click(function(e) { 
        var a = new Array("富强", "民主", "文明", "和谐", "自由", "平等", "公正" ,"法治", "爱国", "敬业", "诚信", "友善"); 
        var $i = $("<span/>").text(a[a_idx]); 
        a_idx = (a_idx + 1) % a.length; 
        var x = e.pageX, 
        y = e.pageY; 
        $i.css({ 
            "z-index": 999, 
            "top": y - 20, 
            "left": x, 
            "position": "absolute", 
            "font-weight": "bold", 
            "color": "#ff6651" 
        }); 
        $("body").append($i); 
        $i.animate({ 
            "top": y - 180, 
            "opacity": 0 
        }, 
        1500, 
        function() { 
            $i.remove(); 
        }); 
    }); 
}); 
</script>
<!--edn--富强--> | 
  <a class="rss" href="https://ArtZoick.github.io//atom.xml" target="_blank">RSS</a>
</div>

<script>
  hljs.initHighlightingOnLoad()

  let mainNavLinks = document.querySelectorAll(".markdownIt-TOC a");

  // This should probably be throttled.
  // Especially because it triggers during smooth scrolling.
  // https://lodash.com/docs/4.17.10#throttle
  // You could do like...
  // window.addEventListener("scroll", () => {
  //    _.throttle(doThatStuff, 100);
  // });
  // Only not doing it here to keep this Pen dependency-free.

  window.addEventListener("scroll", event => {
    let fromTop = window.scrollY;

    mainNavLinks.forEach((link, index) => {
      let section = document.getElementById(decodeURI(link.hash).substring(1));
      let nextSection = null
      if (mainNavLinks[index + 1]) {
        nextSection = document.getElementById(decodeURI(mainNavLinks[index + 1].hash).substring(1));
      }
      console.log('section.offsetHeight', section.offsetHeight);
      if (section.offsetTop <= fromTop) {
        if (nextSection) {
          if (nextSection.offsetTop > fromTop) {
            link.classList.add("current");
          } else {
            link.classList.remove("current");    
          }
        } else {
          link.classList.add("current");
        }
      } else {
        link.classList.remove("current");
      }
    });
  });

</script>

      </div>
    </div>
  </body>
</html>
